# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        return f'val is {self.val} next is {self.next}'


# 21. 合并两个有序链表
# 方法一：使用迭代的方式
# 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。
# 空间复杂度：O(1)。我们只需要常数的空间存放若干变量。
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    head = ListNode(-1)

    re = head

    while list1 and list2:

        if list1.val > list2.val:
            head.next = list2
            list2 = list2.next
        else:
            head.next = list1
            list1 = list1.next

        head = head.next

    if list1 is None:
        head.next = list2

    if list2 is None:
        head.next = list1

    return re.next


# 方法二：使用递归的方式
# 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。
# 因此，时间复杂度取决于合并后的链表长度，即 O(n+m)O(n+m)O(n+m)。

# 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。
# 递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。
# 结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。
def mergeTwoLists_2(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if list1 is None:
        return list2
    if list2 is None:
        return list1

    if list1.val > list2.val:
        list2.next = mergeTwoLists_2(list1, list2.next)
        return list2
    else:
        list1.next = mergeTwoLists_2(list1.next, list2)
        return list1


# [1, 3, 5]
node_5 = ListNode(5)
node_3 = ListNode(3, node_5)
node_1 = ListNode(1, node_3)

# [2, 4, 6]
node_6 = ListNode(6)
node_4 = ListNode(4, node_6)
node_2 = ListNode(2, node_4)

result = mergeTwoLists_2(node_1, node_2)
print(f"result:{result}")
